`
https://leetcode.cn/problems/lfu-cache/
`

class LFUCache {
  constructor(capacity) {
    // key 到 val 的映射
    this.keyToVal = new Map()
    // key 到 freq 的映射
    this.keyToFreq = new Map()
    // freq 到 key 的映射
    this.freqToKeys = new Map()
    // 记录最小的频率
    this.minFreq = 0
    // 缓存容量
    this.capacity = capacity
  }

  get(key) {
    // 没找到返回 -1
    if (!this.keyToVal.has(key)) return -1

    // 访问频率 + 1
    this._increaseFreq(key)
    return this.keyToVal.get(key)
  }

  put(key, val) {
    if (this.capacity <= 0) return

    // 如果缓存里已经有 key，更新值和频率即可
    if (this.keyToVal.has(key)) {
      this.keyToVal.set(key, val)
      this._increaseFreq(key)
      return
    }

    // 容量已满的话需要淘汰一个 freq 最小的 key
    if (this.capacity <= this.keyToVal.size) {
      this._removeMinFreqKey()
    }

    // 插入新的缓存
    this.keyToVal.set(key, val)
    this.keyToFreq.set(key, 1)
    if (!this.freqToKeys.has(1)) {
      this.freqToKeys.set(1, new Set())
    }
    this.freqToKeys.get(1).add(key)
    // 插入新 key 后 minFreq 一定是 1
    this.minFreq = 1
  }

  // 增加 key 的访问频率
  _increaseFreq(key) {
    // 获取当前 key 的原本频率
    const curFreq = this.keyToFreq.get(key)
    // 更新当前 key 的新频率
    this.keyToFreq.set(key, curFreq + 1)
    // 删除对应频率列表里面的 key
    this.freqToKeys.get(curFreq).delete(key)
    // 如果没有新的频率对应的列表就先创建
    if (!this.freqToKeys.has(curFreq + 1)) {
      this.freqToKeys.set(curFreq + 1, new Set())
    }
    // 把 key 放到新的频率对应的列表里
    this.freqToKeys.get(curFreq + 1).add(key)
    // 如果原本的频率列表空了，就删掉
    if (this.freqToKeys.get(curFreq).size === 0) {
      this.freqToKeys.delete(curFreq)
      // 如果这个 freq 恰好是 minFreq，更新 minFreq
      if (curFreq === this.minFreq) {
        this.minFreq++
      }
    }
  }

  // 淘汰 freq 最小的 key
  _removeMinFreqKey() {
    // 获取 freq 最小的列表
    const minFreqList = this.freqToKeys.get(this.minFreq)
    // 获取 freq 最小列表的第一个元素
    const deleteKey = minFreqList.values().next().value
    // 删掉获取到的元素
    minFreqList.delete(deleteKey)
    // 如果删完后列表空了
    if (minFreqList.length === 0) {
      // 就删掉列表
      this.freqToKeys.delete(this.minFreq)
    }
    // 删除最小 key 对应的记录
    this.keyToVal.delete(deleteKey)
    this.keyToFreq.delete(deleteKey)
  }
}

/** 
* Your LFUCache object will be instantiated and called as such:
* var obj = new LFUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/

// test
const lfu = new LFUCache(2)
lfu.put(1, 1)
lfu.put(2, 2)
lfu.get(1)
lfu.put(3, 3)
lfu.get(2)
lfu.get(3)
lfu.put(4, 4)
lfu.get(1)
lfu.get(3)
lfu.get(4)